package com.rui.shangXueTang.select;

import java.util.Arrays;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : FibonacciSelect
 * @createTime : [2022/2/16 15:31]
 * @description : [斐波那契查找算法]
 */

public class FibonacciSelect {
    public static void main(String[] args) {
        //斐波那契数列
        int[] arr = {1,1,2,3,5,8,13,21,34,55,89};
        int index = select(arr, 13);
        System.out.println(index);
    }

    private static int select(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;
        int k = 0;
        int mid = 0;
        int[] fib = fibonacci(20);

        //找分割点
        while(right > fib[k] - 1){
            k++;
        }

        int[] temp = Arrays.copyOf(arr,fib[k]);

        for(int i = right + 1 ; i < temp.length ; i++){
            temp[i] = arr[right];
        }

        while(left <= right){
            mid = left + fib[k-1] - 1;
            if(target < temp[mid]){
                k--;
            }else if(target > temp[mid]){
                left = mid + 1;
                k -= 2;
            }else {
                if(mid <= right){
                    return mid;
                }else {
                    return right;
                }
            }
        }
        return -1;
    }

    /**
     * 产生斐波那契数列
     * @param n 数列长度
     * @return int[]
     */
    private static int[] fibonacci(int n){
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 1;
        for(int i = 2 ; i < n ; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr;
    }
}
